package com.lw.leetcode.greedy.c;

import com.lw.test.util.Utils;

import java.util.Arrays;
import java.util.Comparator;

/**
 * Created with IntelliJ IDEA.
 * 2412. 完成所有交易的初始最少钱数
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/17 13:38
 */
public class MinimumMoney {

    public static void main(String[] args) {
        MinimumMoney test = new MinimumMoney();

        // 10
//        int[][] arr ={{2,1},{5,0},{4,2}};

        // 14
//        int[][] arr = {{6, 9},{2, 3},{1, 4},{5, 4},{8, 3},{5, 7},{0, 9},{4, 9},{5, 3}};

        //
        int[][] arr = Utils.getArr(10000, 2, 0, 1000);

        long l = test.minimumMoney(arr);
        System.out.println(l);
    }

    public long minimumMoney(int[][] transactions) {
        int s1 = 0;
        int s2 = 0;
        int eq = 0;
        for (int[] transaction : transactions) {
            int a = transaction[0];
            int b = transaction[1];
            if (a < b) {
                s2++;
            } else if (a > b) {
                s1++;
            } else {
                eq = Math.max(eq, a);
            }
        }
        int[][] arr1 = new int[s1][2];
        int[][] arr2 = new int[s2][2];
        for (int[] transaction : transactions) {
            int a = transaction[0];
            int b = transaction[1];
            if (a < b) {
                int[] ints = arr2[--s2];
                ints[0] = a;
                ints[1] = b;
            } else if (a > b) {
                int[] ints = arr1[--s1];
                ints[0] = a;
                ints[1] = b;
            }
        }
        Arrays.sort(arr1, (a, b) -> a[1] == b[1] ? Integer.compare(b[0], a[0]) : Integer.compare(a[1], b[1]));
        long sum = 0;
        long item = 0;
        for (int[] transaction : arr1) {
            int a = transaction[0];
            int b = transaction[1];
            if (a < item) {
                item = item - a + b;
            } else {
                sum += (a - item);
                item = b;
            }
        }
        if (item < eq) {
            sum += (eq - item);
            item = eq;
        }
        Comparator<int[]> c = (a, b) -> a[0] == b[0] ? Integer.compare(a[1], b[1]) : Integer.compare(b[0], a[0]);

        Arrays.sort(arr2, c);
        for (int[] transaction : arr2) {
            int a = transaction[0];
            int b = transaction[1];
            if (a < item) {
                item = item - a + b;
            } else {
                sum += (a - item);
                item = b;
            }
        }
        return sum;
    }


}
